class EXP

EXP, exponential-time algorithm
#complexity_theory

Definition

Define the class $\mathbf{EXP} = \cup_{c \geq 1} \mathbf{DTIME}(2^{n^c})$ .

Notes

exponential-time analog of P
$\mathbf{P} \subseteq \mathbf{NP} \subseteq \mathbf{EXP}$

References

D. P. Williamson, D. B. Shmoys. Approximation Algorithms, Cambridge University Press, 2010, pp. 41, 56-57.